package org.example.game.weekly.game409;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import static com.sun.javafx.scene.traversal.Hueristic2D.findMin;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/08/03 20:46
 */
public class Solution002 {

    public static void main(String[] args) {
        int[] res = new Solution002().shortestDistanceAfterQueries(5, new int[][]{{2,4}});
        for (int re : res) {
            System.out.println(re);
        }
    }
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int[] res = new int[queries.length];
        List<int[]> roadList = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            roadList.add(queries[i]);
            res[i] = findShortRoad(0, n-1, roadList);
        }
        return res;
    }

    //不是选最长，是选 相连最长
    private int findShortRoad(int start, int end, List<int[]> roadList) {
        if(start == end){
            return 0;
        }
        if(end - start == 1){
            return 1;
        }
        if(start > end){
            return 0;
        }

        List<Integer> mergerCountList = new ArrayList<>();
        List<int[]> mergerRoadList = new ArrayList<>();

        HashMap<Integer, List<Integer>> startEndRoadMap = new HashMap<>();
        //合并路径 记录合并次数
        for (int[] road : roadList) {
            if(road[0] < start || road[1] > end){
                //不在目标范围
                continue;
            }
            int start1 = Math.min(road[0], road[1]);
            int end1 = Math.max(road[0], road[1]);
            startEndRoadMap.putIfAbsent(start1, new ArrayList<>());
            startEndRoadMap.get(start1).add(road[end1]);
        }

        for (int[] road : roadList) {
            if (road[0] < start || road[1] > end) {
                //不在目标范围
                continue;
            }
            int mergerCount = 0;

            int start1 = Math.min(road[0], road[1]);
            int end1 = Math.max(road[0], road[1]);
            while (startEndRoadMap.containsKey(end1)){
                List<Integer> endList = startEndRoadMap.get(end1);
                for (Integer nextEnd : endList) {
                    int lastEnd = nextEnd;

                }
            }
        }
        //同起点，保留最长路径

        //

        int sum = 0;
        //找出最长的路 先走
        int max = 1;
        //默认向前走一步
        int[] maxRoad = new int[2];
        maxRoad[0] = start;
        maxRoad[1] = start+1;
        for (int[] road : roadList) {
            if(road[0] < start || road[1] > end){
                //不在目标范围
                continue;
            }
            int dis = Math.abs(road[0]-road[1]);
            if(dis > max){
                max = dis;
                maxRoad = road;
            }
        }
        sum+=1;
        int newStart = 0;
        int newEnd = 0;
        if(maxRoad[0] >= maxRoad[1]){
            newEnd = maxRoad[0];
            newStart = maxRoad[1];
        }else {
            newStart = maxRoad[0];
            newEnd = maxRoad[1];
        }
        //继续找子问题
        if(newStart > start){
            sum+=findShortRoad(start, newStart, roadList);
        }

        if(newEnd < end){
            sum+=findShortRoad(newEnd, end, roadList);
        }
        return sum;
    }

}
